package StackOrQueue;//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
// 
//
// 示例 2： 
//
// 
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
// 
//
// 示例 3： 
//
// 
//输入：s = ""
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3 * 10⁴ 
// s[i] 为 '(' 或 ')' 
// 
// 
// 
// Related Topics 栈 字符串 动态规划 👍 1749 👎 0


import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

//leetcode submit region begin(Prohibit modification and deletion)
class longestValidParentheses {
    public int longestValidParentheses1(String s) {
        /**
         将符合要求的下标位置 置为 0 ， 不符合的为1， 转换为找最多连续的 0
         (()(()))  转换为 10000001
         */
        if(s==null || s.length() == 0){
            return 0;
        }
        int len = s.length();
        int[] mark = new int[len];  //标记数组
        Deque<Integer> que = new ArrayDeque<>();  //栈
        for(int i=0;i<len;i++){
            //如果当前字符是左括号 入栈
            if(s.charAt(i) == '('){
                que.addLast(i);
            }else{
                //不是左括号看能不能和栈顶匹配，不能则标记为1
                if(que.isEmpty()){
                    mark[i] = 1;
                }else{
                    que.pollLast();
                }
            }
        }
        while(!que.isEmpty()){
            mark[que.pollLast()] = 1;
        }
        int res = 0, ans = 0;
        //统计最长的连续0
        for(int i=0; i<len; i++){
            if(mark[i] == 0){
                ans++;
                res = Math.max(res,ans);
            }else{
                ans = 0;
            }
        }
        return res;

    }

    public int longestValidParentheses(String s) {
        if("".equals(s) || s.length()==0){
            return 0;
        }
        //栈解决，栈中存放括号的下标，
        // 具体做法是我们始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        char[] chars = s.toCharArray();
        int maxLen = 0;
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            //如果当前是左括号，将下标入栈
            if(c == '('){
                stack.push(i);
            }else{
                //是右括号就弹出栈顶
                stack.pop();
                //弹完后栈不为空，就计算下标差即长度。
                if(!stack.isEmpty()){
                    maxLen = Math.max(maxLen, i-stack.peek());
                }else{
                    //若为空，表示当前右括号是无法匹配的括号
                    stack.push(i);
                }
            }
        }
        return maxLen;


    }
}
//leetcode submit region end(Prohibit modification and deletion)
